public class num416 {
    public static boolean canPartition(int[] nums) {
        int len = nums.length;
        if(nums.length < 2) {
            return false;
        }
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }
        //和为基数不能分成两个值相等的数组
        if((sum & 1) == 1) {
            return false;
        }
        int target = sum / 2;
        boolean[][] b = new boolean[len][target + 1];
        if(nums[0] < target) {
            b[0][nums[0]] = true;
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < target + 1; j++) {
                b[i][j] = b[i - 1][j];
                if(nums[i] == j) {
                    b[i][j] = true;
                    continue;
                }
                if(nums[i] < j) {
                    b[i][j] = b[i - 1][j] || b[i - 1][j - nums[i]];
                }
            }
        }
        return b[len - 1][target];
    }
}
